Building the adjacency matrix for graph U

  • The adjacency matrix is an n×n matrix where entry adj[i,j] = 1 if there's an edge between vertices i and j, and 0 otherwise. Using the vertex ordering A, B, C, D, we create a 4×4 matrix to represent all possible connections.
  • For an undirected graph, the matrix must be symmetric: adj[i,j] = adj[j,i]. When we place a 1 at position (A,B), we must also place a 1 at position (B,A). This symmetry ensures the bidirectional nature of undirected edges is properly encoded.
  • The diagonal entries adj[i,i] represent self-loops. Since graph U has no self-loops, all diagonal entries are 0. The diagonal runs from top-left to bottom-right and corresponds to edges from each vertex to itself.
  • For the edges A–B, A–C, and B–D, we fill symmetric pairs of cells: (0,1) and (1,0) for A–B; (0,2) and (2,0) for A–C; (1,3) and (3,1) for B–D. All other entries remain 0, indicating no edge exists between those vertex pairs.